#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int maxSubSum1(const vector<int> &IntVec)
{
 int maxSum = 0;
 for (int i = 0; i < IntVec.size(); ++i)
 for (int j = i; j < IntVec.size(); ++j)
 {
  int thisSum = 0;
  for (int k = i; k <= j; ++k)
   thisSum += IntVec[k];

  if (thisSum > maxSum)
   maxSum = thisSum;
 }

 return maxSum;
}

int maxSubSum2(const vector<int> &IntVec)
{
 int maxSum = 0;
 int VecCount = IntVec.size();
 for (int i = 0; i < VecCount; ++i)
 {
  int thisSum = 0;
  for (int j = i; j < VecCount; ++j)
  {
   thisSum += IntVec[j];
   if (thisSum > maxSum)
    maxSum = thisSum;
  }
 }
 return maxSum;
}

int maxSubRec(const vector<int> &IntVec, int left, int right)
{
 if (left == right)
 if (IntVec[left] > 0)
  return IntVec[left];
 else
  return 0;

 int center = (left + right) / 2;
 int LeftSubMax = maxSubRec(IntVec, left, center);
 int RightSubMax = maxSubRec(IntVec, center + 1, right);

 int maxCenterLeftSub = 0, CenterLeftSub = maxCenterLeftSub;
 for (int i = center; i >= left; --i)
 {
  CenterLeftSub += IntVec[i];
  if (CenterLeftSub > maxCenterLeftSub)
   maxCenterLeftSub = CenterLeftSub;
 }

 int maxCenterRightSub = 0, CenterRightSub = maxCenterRightSub;
 for (int i = center + 1; i <= right; ++i)
 {
  CenterRightSub += IntVec[i];
  if (CenterRightSub > maxCenterRightSub)
   maxCenterRightSub = CenterRightSub;
 }

 return max(max(LeftSubMax, RightSubMax),maxCenterLeftSub + maxCenterRightSub);
}

int maxSub3(const vector<int> &IntVec)
{
 return maxSubRec(IntVec, 0, IntVec.size()-1);
}

int maxSub4(const vector<int> &IntVec)
{
 int maxSubSum = 0, thisSum = 0;
 for (int i = 0; i < IntVec.size(); ++i)
 {
  thisSum += IntVec[i];

  if (thisSum < 0)
   thisSum = 0;
  else
  if (thisSum > maxSubSum)
   maxSubSum = thisSum;
 }
 return maxSubSum;
}

int main()
{
 vector<int> nVec = { 1, 2, 3, 4, 5, 6 };
 cout << maxSub4(nVec);
 return 0;
}